import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * Created by IntelliJ
 * Author:熊磊
 */
public class Graph {
    private ArrayList<String> vertexList; //存放节点
    private int[][] edges;  //邻接矩阵
    private int numOfEdges; //有多少条边
    private boolean[] isVisited;

    public static void main(String[] args) {
        int n = 5;
        String[] vertexs = {"A", "B", "C", "D", "E"};
        Graph graph = new Graph(n);
        for (String s : vertexs) {
            graph.insetVertex(s);
        }
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.showGraph();
        graph.dfs();
    }

    //传入节点个数
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        isVisited = new boolean[n];
    }

    //得到第一个邻接节点的下标
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    //根据前一个邻接节点的小标来获取下一个邻接节点
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i == v2; i = (i + 1) % 5) {
            if (edges[v1][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    //深度优先
    public void dfs(boolean[] isVisited, int i) {
        System.out.printf(vertexList.get(i));
        isVisited[i] = true;
        //获得该节点的第一个节点的下标
        int w = getFirstNeighbor(i);
        while (w != -1) {
            if (!isVisited[w]) {
                System.out.printf("->");
                dfs(isVisited, w);
            }
            w = getNextNeighbor(i, w);
        }
    }

    public void bfs(boolean[] isVisited, int i) {
        int u;
        int w;
        LinkedList<Object> queue = new LinkedList<>();
        System.out.println(vertexList.get(i));
        isVisited[i] = true;
        queue.addLast(i);
        while (!queue.isEmpty()) {
            u = (Integer) queue.removeFirst();
            //得到第一个邻接点的下标
            w = getFirstNeighbor(u);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.println(vertexList.get(w));
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                //找到u节点的 w节点的下一个邻接点
                w = getNextNeighbor(u, w);
            }

        }
    }

    //为防止有不连通的节点,我们需要对所有节点都进行广度优先
    public void bfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

    //对dfs进行重载
    public void dfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }


    //返回节点的个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    //返回边的数目
    public int getNumOfEdges() {
        return numOfEdges;
    }

    //返回索引对应的数据
    public String index(int index) {
        return vertexList.get(index);
    }

    //返回边的权值
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    //显示图对应的矩阵
    public void showGraph() {
        System.out.println(" " + vertexList);
        for (int i = 0; i < vertexList.size(); i++) {
            System.out.print(vertexList.get(i));
            System.out.println(Arrays.toString(edges[i]));
        }
    }


    //插入节点
    public void insetVertex(String vertex) {
        vertexList.add(vertex);
    }

    //添加边
    public void insertEdge(int v1, int v2, int weight) {
        if (weight != 1 && weight != 0) {
            System.out.println("weight不能是0或1以外的值");
            return;
        }
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        if (weight == 1) {
            numOfEdges++;
        } else {
            numOfEdges--;
        }

    }

}
